/* 组合计数
    乘法原理，加法原理，组合数，排列数

* 本题:
    牡牛为1，牝牛为0
    f[i]表示所有长度是i的且以1结尾的字符串数量
    f[i] = f[0]+f[1]+...+f[i-k-1] (计算1~i-k-1的前缀和)
    边界情况 f[0] = 1; f[1] = f[0]; 且需要注意i-k-1<0的情况

    优化s[N]存储前缀和
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10, MOD = 5000011;
int n, k;
int f[N], s[N];

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> k;

    f[0] = s[0] = 1;

    for(int i = 1; i <= n; i ++)
    {
        f[i] = s[max(i-k-1, 0)]; //边界控制
        s[i] = (s[i-1] + f[i]) % MOD;
    }
    cout << s[n] << endl;
    return 0;
} //40
